//
// Created by Semir on 2020/6/4.
//

#include "Tree.h"


TreeNode* CreateTreeNode(int value) {
    TreeNode* node = new TreeNode;
    node->val = value;
    node->left = nullptr;
    node->right = nullptr;
    return node;
}

void ConnectTreeNodes(TreeNode* pParent, TreeNode* pLeft, TreeNode* pRight) {
    if(pParent != nullptr) {
        pParent->left = pLeft;
        pParent->right = pRight;
    }
}

void PrintTreeNode(const TreeNode* pNode) {
    if(pNode != nullptr) {
        printf("value of this node is: %d\n", pNode->val);
        if(pNode->left != nullptr)
            printf("value of its left child is: %d.\n", pNode->left->val);
        else
            printf("left child is nullptr.\n");
        if(pNode->right != nullptr)
            printf("value of its right child is: %d.\n", pNode->right->val);
        else
            printf("right child is nullptr.\n");
    } else {
        printf("this node is nullptr.\n");
    }
    printf("\n");
}

//            8
//        6      10
//       5 7    9  11
TreeNode* TestTree1() {

    TreeNode* pNode8 = CreateTreeNode(8);
    TreeNode* pNode6 = CreateTreeNode(6);
    TreeNode* pNode10 = CreateTreeNode(10);
    TreeNode* pNode5 = CreateTreeNode(5);
    TreeNode* pNode7 = CreateTreeNode(7);
    TreeNode* pNode9 = CreateTreeNode(9);
    TreeNode* pNode11 = CreateTreeNode(11);

    ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, pNode9, pNode11);

    return pNode8;
}


//            8
//          7
//        6
//      5
//    4
TreeNode* TestTree2() {

    TreeNode* pNode8 = CreateTreeNode(8);
    TreeNode* pNode7 = CreateTreeNode(7);
    TreeNode* pNode6 = CreateTreeNode(6);
    TreeNode* pNode5 = CreateTreeNode(5);
    TreeNode* pNode4 = CreateTreeNode(4);

    ConnectTreeNodes(pNode8, pNode7, nullptr);
    ConnectTreeNodes(pNode7, pNode6, nullptr);
    ConnectTreeNodes(pNode6, pNode5, nullptr);
    ConnectTreeNodes(pNode5, pNode4, nullptr);

    return pNode8;
}


//            8
//             7
//              6
//               5
//                4
TreeNode* TestTree3() {
    TreeNode* pNode8 = CreateTreeNode(8);
    TreeNode* pNode7 = CreateTreeNode(7);
    TreeNode* pNode6 = CreateTreeNode(6);
    TreeNode* pNode5 = CreateTreeNode(5);
    TreeNode* pNode4 = CreateTreeNode(4);

    ConnectTreeNodes(pNode8, nullptr, pNode7);
    ConnectTreeNodes(pNode7, nullptr, pNode6);
    ConnectTreeNodes(pNode6, nullptr, pNode5);
    ConnectTreeNodes(pNode5, nullptr, pNode4);

    return pNode8;
}


/*
        1
       / \
      2   3
     / \
    4   5
 */
TreeNode* TestTree4() {
    TreeNode* pNode1 = CreateTreeNode(1);
    TreeNode* pNode2 = CreateTreeNode(2);
    TreeNode* pNode3 = CreateTreeNode(3);
    TreeNode* pNode4 = CreateTreeNode(4);
    TreeNode* pNode5 = CreateTreeNode(5);

    ConnectTreeNodes(pNode1, pNode2, pNode3);
    ConnectTreeNodes(pNode3, nullptr, nullptr);
    ConnectTreeNodes(pNode2, pNode4, pNode5);
    ConnectTreeNodes(pNode4, nullptr, nullptr);
    ConnectTreeNodes(pNode5, nullptr, nullptr);

    return pNode1;
}

/*
          1
        /   \
       2     3
     /   \
    4     5
   / \   / \
  6   7 8   9
 */
TreeNode* TestTree5() {
    TreeNode* pNode1 = CreateTreeNode(1);
    TreeNode* pNode2 = CreateTreeNode(2);
    TreeNode* pNode3 = CreateTreeNode(3);
    TreeNode* pNode4 = CreateTreeNode(4);
    TreeNode* pNode5 = CreateTreeNode(5);
    TreeNode* pNode6 = CreateTreeNode(6);
    TreeNode* pNode7 = CreateTreeNode(7);
    TreeNode* pNode8 = CreateTreeNode(8);
    TreeNode* pNode9 = CreateTreeNode(9);

    ConnectTreeNodes(pNode1, pNode2, pNode3);
    ConnectTreeNodes(pNode2, pNode4, pNode5);
    ConnectTreeNodes(pNode3, nullptr, nullptr);
    ConnectTreeNodes(pNode4, pNode6, pNode7);
    ConnectTreeNodes(pNode5, pNode8, pNode9);
    ConnectTreeNodes(pNode6, nullptr, nullptr);
    ConnectTreeNodes(pNode7, nullptr, nullptr);
    ConnectTreeNodes(pNode8, nullptr, nullptr);
    ConnectTreeNodes(pNode9, nullptr, nullptr);

    return pNode1;
}

TreeNode* TestTree6() {
    TreeNode* pNode8 = CreateTreeNode(8);
    TreeNode* pNode6 = CreateTreeNode(6);
    TreeNode* pNode10 = CreateTreeNode(10);
    TreeNode* pNode5 = CreateTreeNode(5);
    TreeNode* pNode7 = CreateTreeNode(7);
    TreeNode* pNode9 = CreateTreeNode(9);
    TreeNode* pNode11 = CreateTreeNode(11);

    ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, pNode9, pNode11);

    return pNode8;
}